/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package graf;

import java.util.ArrayList;

/**
 *
 * @author sufka
 */
public class Sciezka {

    ArrayList<Wierzcholek> naSciezce;
    boolean odwiedzony;

    public Sciezka() {
        this.naSciezce = new ArrayList<Wierzcholek>();
        this.odwiedzony = false;
    }

    public Sciezka(Sciezka s) {
        this.naSciezce = new ArrayList<Wierzcholek>();
        for (Wierzcholek w : s.getNaSciezce()) {
            this.naSciezce.add(w);
        }
        this.odwiedzony = false;
    }

    public void dodajNaPoczatek(Wierzcholek w){
        this.naSciezce.add(0, w);
    }

    public void dodajNaKoniec(Wierzcholek w) {
        this.naSciezce.add(w);
    }

    public int dlugoscSciezki() {
        return this.naSciezce.size();
    }

    public Wierzcholek usunOstatni() {
        if (this.naSciezce.size() > 0) {
            return this.naSciezce.remove(this.naSciezce.size() - 1);
        }
        return null;
    }

    public Wierzcholek usunZPozycji(int i) {
        if (i < this.naSciezce.size()) {
            return this.naSciezce.remove(i);
        }
        return null;
    }

    public Wierzcholek pierwszy() {
        if (this.naSciezce.size() > 0) {
            return this.naSciezce.get(0);
        }
        return null;
    }

    public Wierzcholek ostatni() {
        if (this.naSciezce.size() > 0) {
            return this.naSciezce.get(this.naSciezce.size() - 1);
        }
        return null;
    }

    public void czyscSciezke() {
        this.naSciezce.clear();
    }

    public ArrayList<Wierzcholek> getNaSciezce() {
        return this.naSciezce;
    }

    public boolean czyNaSciezce(Wierzcholek w) {
        return this.naSciezce.contains(w);
    }

    public Wierzcholek podajZPozycji(int i) {
        if (i < this.dlugoscSciezki()) {
            return this.naSciezce.get(i);
        }
        return null;
    }

    public boolean isOdwiedzony() {
        return odwiedzony;
    }

    public void setOdwiedzony(boolean odwiedzony) {
        this.odwiedzony = odwiedzony;
    }

    public boolean czyZawieraSciezke(Sciezka s) {
        if (this.dlugoscSciezki() < s.dlugoscSciezki()) {
            return false;
        }
        Wierzcholek poczatek = s.pierwszy();
        int nr = 0;
        for (int i = 0; i < this.dlugoscSciezki(); ++i) {
            if (this.getNaSciezce().get(i).getNumer() == poczatek.getNumer()) {
                nr = i;
                if(this.dlugoscSciezki() - nr < s.dlugoscSciezki()){
                    return false;
                }
                break;
            }
        }
        for(int i = 0; i < s.dlugoscSciezki(); ++i){
            if(s.getNaSciezce().get(i).getNumer() != this.getNaSciezce().get(nr + i).getNumer()){
                return false;
            }
        }
        return true;
    }

    public boolean czyZawieraSekwencjeSciezkaPoboczna(Sciezka s) {
        if (this.dlugoscSciezki() < s.dlugoscSciezki()) {
            return false;
        }
        int nr = 0; //indeks wierzcholka ze sciezki - jako argument
        boolean numerZauwazono = false;
        for (int i = 0; i < this.dlugoscSciezki(); ++i) {
            if(numerZauwazono){
                if(this.getNaSciezce().get(i).getNumer() != s.podajZPozycji(nr).getNumer()){
                    nr--;
                }
                numerZauwazono = false;
            }
            if (this.getNaSciezce().get(i).getNumer() == s.podajZPozycji(nr).getNumer()) {
                numerZauwazono = true;
                nr++;
                if (nr == s.dlugoscSciezki()){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean czyZawieraSekwencjeObjazd(Sciezka s) {
        if (this.dlugoscSciezki() < s.dlugoscSciezki()) {
            return false;
        }
        int nr = 0; //indeks wierzcholka ze sciezki - jako argument
        for (int i = 0; i < this.dlugoscSciezki(); ++i) {
            if (this.getNaSciezce().get(i).getNumer() ==
                    s.podajZPozycji(nr).getNumer()) {
                nr++;
                if (nr == s.dlugoscSciezki()){
                    return true;
                }
            }
        }
        return false;
    }

    public Sciezka czyMoznaScalic(Sciezka s){
        //sa dwie mozliwosci scalania sciezek (testow)
        //1. aktualna sciezka (rozszerzajaca) ma zakonczenia taie jak sciezka argument i
        // co wskazue an to ze mozliwe jest, ze rozszerzy argument
        //2. konce sciezek sa rozne i mozliwe jest, ze aktualna sciezka moze sie rozserzyc
        //o wszystkie elementy bedace w petli w argumentcie, jesli tylko istnieje w aktualnej sciezce
        //element bedacy spojnikiem w argumencie
        int indL1 = 0;
        int indL2 = Integer.MAX_VALUE;
        int indP1 = s.dlugoscSciezki()-1; //???
        int indP2 = -1;
        for(int i = 0; i < this.dlugoscSciezki(); ++i){
            if(this.podajZPozycji(i).getNumer() == s.podajZPozycji(indL1).getNumer()){
                indL2 = i;
                break;
            }
        }
        for(int i = this.dlugoscSciezki()-1; i > -1; --i){
            if(this.podajZPozycji(i).getNumer() == s.podajZPozycji(indP1).getNumer()){
                indP2 = i;
                break;
            }
        }
        if(indL2 == 0 && indP2 == this.dlugoscSciezki()-1){
            //wersja pierwsza
            int numerLewy = this.podajZPozycji(indL2).getNumer();
            int numerPrawy = this.podajZPozycji(indP2).getNumer();
            int indeks = -1, ile = Integer.MAX_VALUE, noweIle = 0;
            int lewyTemp;
            //tu szukamy najkrotszej petelki w aktualnej sciezce
            for(int i = indL2; i < indP2+1; ++i){
                lewyTemp = this.podajZPozycji(i).getNumer();
                for(int j = indP2; j > i-1; --j){
                    if(j > i && this.podajZPozycji(j).getNumer() == lewyTemp){
                        if(j-i < ile){
                            ile = j-i;
                            indeks = i;
                        }
                    }
                }
            }
            if(indeks == -1){
                return null;
            }
            //indeks = poczatek petelki, ile = dlugosc petelki
            //tworzymy pseudo sceizke bez petelki i sprawedamy czy jest ona sekwencja w argumencie
            //jesli tak to laczymy argument  z petelka i zwracamy jako wynik metody
            Sciezka sPseudo = new Sciezka();
            for(int i = 0; i < indeks; ++i){
                sPseudo.dodajNaKoniec(this.podajZPozycji(i));
            }
            for(int i = indeks+ile; i < this.dlugoscSciezki(); ++i){
                sPseudo.dodajNaKoniec(this.podajZPozycji(i));
            }

            if(s.czyZawieraSekwencjeObjazd(sPseudo)){
                //jesli tak to dolacz petle do argumentu
                Sciezka sNew = new Sciezka();
                int stop = -1;
                for(int i = 0; i < s.dlugoscSciezki(); ++i){
                    if(s.podajZPozycji(i).getNumer() != this.podajZPozycji(indeks).getNumer()){
                        sNew.dodajNaKoniec(s.podajZPozycji(i));
                    }else{
                        stop = i;
                        break;
                    }
                }
                for(int i = indeks; i < indeks+ile; ++i){
                    sNew.dodajNaKoniec(this.podajZPozycji(i));
                }
                for(int i = stop; i < s.dlugoscSciezki(); ++i){
                    sNew.dodajNaKoniec(s.podajZPozycji(i));
                }
                return sNew;
            }
            return null;

//            int indexL1 = indL1+1, indexP1 = indP1-1;
//            int indexL2 = indL2+1, indexP2 = indP2-1;
//            int numerLewy = s.podajZPozycji(indL1).getNumer(),
//                    numerPrawy = s.podajZPozycji(indP1).getNumer();
//            for(int i = indL1+1 ; i < indP1; ++i){
//                if(s.podajZPozycji(i).getNumer() == this.podajZPozycji(indexL2).getNumer()){
//                    numerLewy = s.podajZPozycji(i).getNumer();
//                    indexL2++;
//                }else{
//                    indexL2--;
//                    indexL1 = i-1;
//                    break;
//                }
//            }
//            for(int i = indP1-1 ; i > indL1; --i){
//                if(s.podajZPozycji(i).getNumer() == this.podajZPozycji(indexP2).getNumer()){
//                    numerPrawy = s.podajZPozycji(i).getNumer();
//                    indexP2--;
//                }else{
//                    indexP2++;
//                    indexP1 = i+1;
//                    break;
//                }
//            }
//
//            if(numerLewy == numerPrawy){
//                //scalamy z aktualnego do s i zwracamy wynik z s
//                Sciezka sNew = new Sciezka();
//                for(int i = 0 ; i < indexL1; ++i){
//                    sNew.dodajNaKoniec(s.podajZPozycji(i));
//                }
//                for(int i = indexL2; i < indexP2; ++i){
//                    sNew.dodajNaKoniec(this.podajZPozycji(i));
//                }
//                for(int i = indexL1; i < s.dlugoscSciezki(); ++i){
//                    sNew.dodajNaKoniec(s.podajZPozycji(i));
//                }
//                return sNew;
//            }else{
//                //nie mozna scalic
//                return null;
//            }
        }else if (indP2 >= indL2){
            //wersja druga
            //szukam najdluzszej petli w argumencie
//            int indeks = -1;
//            int ile = 0;
//            for(int i = indP1; i < indP1+1; ++i){
//                int symbol = this.podajZPozycji(i).getNumer();
//                for(int j = indL1; )
//
//            }
        }

        return null;
    }

    public boolean czyTestowa(Graf g){
        if(g.getPoczatkowe().contains(this.pierwszy()) && g.getKoncowe().contains(this.ostatni())){
            return true;
        }
        return false;
    }

    public boolean isTestPath(Graf g){
	return g.isPoczatkowy(this.getNaSciezce().get(0)) &&
	       g.isKoncowy(this.getNaSciezce().get(this.dlugoscSciezki()-1));
    }

    public boolean containsPath(Sciezka path){
	int[] values = new int[3];// values == start, end, len;
	intersectionLeftPos(path, values);

	if(values[2] == path.dlugoscSciezki()){
            return true;
        }
	return false;
    }

    public void intersectionLeftPos(Sciezka path, int[] values){
	int maxLen = 0;
	int maxStart = -1;
	int maxEnd = -1;
	int tmpStart = this.getNaSciezce().indexOf(path.getNaSciezce().get(0));
	while(tmpStart != -1){
            int j = 1;
            int tmpEnd = -1;

            for(int i = tmpStart + 1; i < this.dlugoscSciezki(); ++i){
		if(j == path.dlugoscSciezki() || this.getNaSciezce().get(i) != path.getNaSciezce().get(j)){
                    tmpEnd = i - 1;
                    break;
		}
        	++j;
            }

            if(tmpEnd == -1){
                tmpEnd = this.dlugoscSciezki() - 1;
            }
            int len = tmpEnd - tmpStart + 1;
            /* >= because in case we've got many intersections of the same length
               we want the last one
            */
            if(len >= maxLen){
                maxLen = len;
                maxStart = tmpStart;
                maxEnd = tmpEnd;
            }

            tmpStart = this.indexOfNext(path.getNaSciezce().get(0), tmpStart + 1);         

            values[0] = maxStart;
            values[1] = maxEnd;
            values[2] = maxLen;

        }
    }

    public int indexOfNext(Wierzcholek w, int start){
        for(int i = start; i < this.dlugoscSciezki(); ++i){
            if(this.getNaSciezce().get(i).equals(w)){
                return i;
            }
        }
        return -1;
    }

    public int intersects(Sciezka path){
	int sza = intersectsLeft(path);
	int szb = intersectsRight(path);

	if(sza > szb){
            return sza;
        }
	return szb;
    }

    public int intersectsLeft(Sciezka path){
	int[] values = new int[3];// values = start, end, len;

	intersectionLeftPos(path, values);

	if(values[1] == (this.dlugoscSciezki() - 1)){
            return values[2];
        }
	return 0;
    }

    public int intersectsRight(Sciezka path){
	return path.intersectsLeft(this);
    }

    public boolean isBorderPath(Graf g){
	return g.isKoncowy(this.ostatni()) ||
	       g.isPoczatkowy(this.pierwszy());
    }

    public Sciezka mergedWith(Sciezka path){
	int[] valuesLeft = new int[3];//valuesLeft = startLeft, endLeft, lenLeft;
	int[] valuesRight = new int[3]; //valuesRight = startRight, endRight, lenRight;

	intersectionLeftPos(path, valuesLeft);
	intersectionRightPos(path, valuesRight);


	boolean leftMergePossible = (valuesLeft[1] == (this.dlugoscSciezki() - 1)) && (valuesLeft[2] != 0);
	boolean rightMergePossible = (valuesRight[1] == (path.dlugoscSciezki() - 1)) && (valuesRight[2] != 0);

	boolean mergeLeft = false;
	boolean mergeRight = false;

	if(leftMergePossible && !rightMergePossible){
            mergeLeft = true;
        }
	if(rightMergePossible && !leftMergePossible){
            mergeRight = true;
        }
	if(rightMergePossible && leftMergePossible){
            if(valuesLeft[2] >= valuesRight[2]){
                mergeLeft = true;
            }else{
                mergeRight = true;
            }
	}

	if(mergeLeft){
            Sciezka newPath = new Sciezka();
            for(int i = 0; i < this.dlugoscSciezki(); ++i){
                newPath.dodajNaKoniec(this.podajZPozycji(i));
            }

            int from = this.dlugoscSciezki() - valuesLeft[0];
            for(int i = from; i < path.dlugoscSciezki(); ++i){
                newPath.dodajNaKoniec(path.podajZPozycji(i));
            }
            return newPath;
	}

	if(mergeRight){
            Sciezka newPath = new Sciezka();
            for(int i = 0; i < path.dlugoscSciezki(); ++i){
                newPath.dodajNaKoniec(path.podajZPozycji(i));
            }
            int from = path.dlugoscSciezki() - valuesRight[1];

            for(int i = from; i < this.dlugoscSciezki(); ++i){
                newPath.dodajNaKoniec(this.podajZPozycji(i));
            }
            return newPath;
	}

	return null;
    }

    public void intersectionRightPos(Sciezka path, int[] values){
	path.intersectionLeftPos(this, values);
    }

    public void appendPath(Sciezka path){
	for(Wierzcholek w: path.getNaSciezce()){
            this.dodajNaKoniec(w);
	}
    }

    public void prependPath(Sciezka path){
	for(int i = path.dlugoscSciezki() - 1; i >= 0; --i){
            this.dodajNaPoczatek(path.podajZPozycji(i));
	}
    }

    public int edgeCount(){
        return this.dlugoscSciezki()-1;
    }
}
